package org.example.top40;

public class main10 {
    //最长回文字串
    //输入：s = "babad"
    //输出："bab"
    //思路：二维dp
    //暴力求解需要 记录begin maxLen 最后用substring
    public static void main(String[] args) {
        String s="babad";
        int len=s.length();
        int begin=0;


        int maxLen=1;
        for (int i = 0; i < len-1; i++) {
            for (int j = i+1; j < len; j++) {
                if(j-i+1>maxLen&&validHuiWen(i,j,s)){
                    begin=i;
                    maxLen=j-i+1;
                }
            }
        }
        System.out.println(s.substring(begin,begin+maxLen));
    }

    private static boolean validHuiWen(int i, int j, String s) {
        while (i<j){
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

}
